Shor's algorithm is a quantum computer algorithm for finding the prime factors of an integer. It was developed in 1994 by the American mathematician Peter Shor.

On a quantum computer, to factor an integer ${\displaystyle N}$, Shor's algorithm runs in polylogarithmic time, meaning the time taken is polynomial in ${\displaystyle \log N}$, the size of the integer given as input. Specifically, it takes quantum gates of order ${\displaystyle O\!\left((\log N)^{2}(\log \log N)(\log \log \log N)\right)}$ using fast multiplication, or even ${\displaystyle O\!\left((\log N)^{2}(\log \log N)\right)}$ utilizing the asymptotically fastest multiplication algorithm currently known due to Harvey and Van Der Hoven, thus demonstrating that the integer factorization problem can be efficiently solved on a quantum computer and is consequently in the complexity class BQP. This is almost exponentially faster than the most efficient known classical factoring algorithm, the general number field sieve, which works in sub-exponential time: ${\displaystyle O\!\left(e^{1.9(\log N)^{1/3}(\log \log N)^{2/3}}\right)}$. The efficiency of Shor's algorithm is due to the efficiency of the quantum Fourier transform, and modular exponentiation by repeated squarings.

If a quantum computer with a sufficient number of qubits could operate without succumbing to quantum noise and other quantum-decoherence phenomena, then Shor's algorithm could be used to break public-key cryptography schemes, such as

• The RSA scheme
• The Finite Field Diffie-Hellman key exchange
• The Elliptic Curve Diffie-Hellman key exchange

RSA is based on the assumption that factoring large integers is computationally intractable. As far as is known, this assumption is valid for classical (non-quantum) computers; no classical algorithm is known that can factor integers in polynomial time. However, Shor's algorithm shows that factoring integers is efficient on an ideal quantum computer, so it may be feasible to defeat RSA by constructing a large quantum computer. It was also a powerful motivator for the design and construction of quantum computers, and for the study of new quantum-computer algorithms. It has also facilitated research on new cryptosystems that are secure from quantum computers, collectively called post-quantum cryptography.

In 2001, Shor's algorithm was demonstrated by a group at IBM, who factored ${\displaystyle 15}$ into ${\displaystyle 3\times 5}$, using an NMR implementation of a quantum computer with ${\displaystyle 7}$ qubits. After IBM's implementation, two independent groups implemented Shor's algorithm using photonic qubits, emphasizing that multi-qubit entanglement was observed when running the Shor's algorithm circuits. In 2012, the factorization of ${\displaystyle 15}$ was performed with solid-state qubits. Later, in 2012, the factorization of ${\displaystyle 21}$ was achieved. In 2019 an attempt was made to factor the number ${\displaystyle 35}$ using Shor's algorithm on an IBM Q System One, but the algorithm failed because of accumulating errors. Though larger numbers have been factored by quantum computers using other algorithms, these algorithms are similar to classical brute-force checking of factors, so unlike Shor's algorithm, they are not expected to ever perform better than classical factoring algorithms.